{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "integer_partition_problem_sqa.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyOD3gg85xl+5wL3SAfmW/HJ",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/yskmt2018/quantum/blob/master/integer_partition_problem_sqa.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2bRFMj_Xzpek",
        "colab_type": "text"
      },
      "source": [
        "# Integer Partition Problem with Simulated Quantum Annealing\n",
        "\n",
        "* This notebook was created and tested on Google Colaboratory. (2020/09)\n",
        "\n",
        "## Reference\n",
        "\n",
        "> https://github.com/recruit-communications/pyqubo/blob/master/notebooks/japanese/integer_partition.ipynb"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UIyxo7A5zxIu",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "5cd3436f-5cb4-413c-d343-2075b872222b"
      },
      "source": [
        "!python -V\n",
        "!pip install --quiet pyqubo openjij"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Python 3.6.9\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FK4FQiYI0Bxu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import random\n",
        "import pyqubo\n",
        "from openjij import SQASampler"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yEsc3SWq0OFj",
        "colab_type": "text"
      },
      "source": [
        "## Problem Settings\n",
        "\n",
        "* 整数集合$S$が与えられる。値の和の差が0になるような二つの集合$A,B$に分割したい。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xmiD7H582XVH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def random_integer(element_number):\n",
        "  I = set()\n",
        "  while len(I) < element_number:\n",
        "    e = random.randrange(4, element_number*10, 4)\n",
        "    I.add(e)\n",
        "  \n",
        "  return I"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4yuaNyHa0QlZ",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        },
        "outputId": "c3ae1053-f44a-43c7-96a9-aafdd2210aeb"
      },
      "source": [
        "# Set of Integers\n",
        "S = random_integer(100)\n",
        "\n",
        "print('S : {}'.format(S))\n",
        "print('sum:{}, len:{}'.format(sum(S), len(S)))"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "S : {516, 4, 520, 524, 16, 20, 536, 28, 544, 36, 556, 560, 48, 56, 576, 80, 92, 96, 616, 108, 120, 632, 640, 128, 132, 644, 144, 660, 148, 664, 156, 680, 684, 172, 688, 692, 180, 696, 184, 700, 704, 196, 204, 208, 212, 728, 732, 744, 748, 756, 760, 764, 768, 772, 784, 272, 788, 280, 284, 288, 804, 808, 816, 828, 832, 840, 340, 348, 872, 376, 904, 400, 404, 408, 416, 420, 424, 936, 940, 944, 440, 952, 444, 956, 960, 448, 968, 456, 460, 972, 976, 980, 984, 472, 476, 480, 484, 496, 500, 504}\n",
            "sum:51736, len:100\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Yj9nG3ub96le",
        "colab_type": "text"
      },
      "source": [
        "## Formulation\n",
        "\n",
        "* IPP の目的関数を定式化し、QUBO（Quadratic Unconstrained Binary Optimization）式を構築する。\n",
        "\n",
        "* QUBO 式の構築には、OSS ライブラリ PyQUBO（[GitHub](https://github.com/recruit-communications/pyqubo), [Documentation](https://pyqubo.readthedocs.io/en/latest/)）を用いる。"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "K9Uj4fF9-X9Q",
        "colab_type": "text"
      },
      "source": [
        "### QUBO: Objective Function\n",
        "\n",
        "* 目的関数：二つの集合の値の和の差"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PQFF-PE0-XVQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def build_objective():\n",
        "  H = 0.0\n",
        "  for s in S:\n",
        "    H += s * pyqubo.Spin('{}'.format(s))\n",
        "\n",
        "  return H**2"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KfuXhpHLBAFD",
        "colab_type": "text"
      },
      "source": [
        "### Hamiltonian\n",
        "\n",
        "* 目的関数からハミルトニアン H を定義する。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PJO_VEEx_dt2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "H = build_objective()\n",
        "model = H.compile()\n",
        "qubo, constant = model.to_qubo()"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XydviwA_BjiO",
        "colab_type": "text"
      },
      "source": [
        "## Execute Quantum Annealing\n",
        "\n",
        "* Sampler と呼ばれるモジュールを生成し、構築した QUBO 式を渡すことで、量子アニーリングを実行する。\n",
        "\n",
        "* 結果は、Response オブジェクトとして返却される。"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TEPzuvzUMWKQ",
        "colab_type": "text"
      },
      "source": [
        "### OpenJij\n",
        "\n",
        "* OpenJij（[GitHub](https://github.com/OpenJij/OpenJij), [Documentation](https://openjij.github.io/OpenJij_Documentation/build/html/), [Tutorial](https://openjij.github.io/OpenJijTutorial/build/html/ja/index.html)）\n",
        "\n",
        "* OSS として、量子アニーリングをシミュレートする SQA（Simulated Quantum Annealing）の Python 用 API を提供している。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oBe1ssRyBd_A",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "sampler = SQASampler(num_reads=10)"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cZoYfRBkBodO",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "c75275cf-e976-4ea8-ed5f-70f26a8972f8"
      },
      "source": [
        "%%time\n",
        "response = sampler.sample_qubo(qubo)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CPU times: user 1.35 s, sys: 853 ms, total: 2.2 s\n",
            "Wall time: 1.18 s\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "f5oKUmztMeTd",
        "colab_type": "text"
      },
      "source": [
        "### Take Solutions\n",
        "\n",
        "* Response オブジェクトに格納されている量子アニーリングの結果（解）を取り出す。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ak3USr2HBsKB",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def extract_samples(response):\n",
        "  solutions = []\n",
        "  energies = []\n",
        "  \n",
        "  for record in response.record:\n",
        "    sol, num_occ = record[0], record[2]\n",
        "    solution, _, energy = model.decode_solution(dict(zip(response.variables, sol)), vartype='BINARY')\n",
        "    solutions += [solution] * num_occ\n",
        "    energies += [energy] * num_occ\n",
        "  \n",
        "  return solutions, energies"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SMta9cI-BurX",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "solutions, energies = extract_samples(response)\n",
        "best_solution = solutions[energies.index(min(energies))]"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SNnkBmE2MljB",
        "colab_type": "text"
      },
      "source": [
        "### Print Integer Partition\n",
        "\n",
        "* 二つの集合$A,B$及び値の和の差を表示する。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2D0gRbmTPdr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "A = set()\n",
        "B = set()\n",
        "\n",
        "for (k, v) in best_solution.items():\n",
        "  if v == 0:\n",
        "    A.add(int(k))\n",
        "  else:\n",
        "    B.add(int(k))"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AYn7NNzZB6O3",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 160
        },
        "outputId": "a15072a7-7546-490f-ff0d-b82e342ceb96"
      },
      "source": [
        "print('A : {}'.format(A))\n",
        "print('sum:{}, len:{}'.format(sum(A), len(A)))\n",
        "print('=================')\n",
        "print('B : {}'.format(B))\n",
        "print('sum:{}, len:{}'.format(sum(B), len(B)))\n",
        "print('=================')\n",
        "print('diff:{}'.format(abs(sum(A)-sum(B))))"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "A : {128, 640, 132, 4, 644, 520, 16, 784, 148, 20, 408, 664, 156, 288, 416, 36, 804, 936, 172, 556, 940, 688, 180, 692, 440, 696, 952, 444, 700, 828, 576, 196, 840, 972, 208, 976, 212, 340, 728, 984, 120, 348, 476, 480, 96, 484, 632, 748, 496, 760, 376, 764}\n",
            "sum:25844, len:52\n",
            "=================\n",
            "B : {768, 516, 772, 904, 524, 144, 272, 400, 404, 660, 788, 280, 536, 284, 28, 544, 420, 424, 680, 808, 684, 48, 560, 816, 944, 184, 56, 956, 448, 704, 832, 960, 456, 968, 204, 460, 80, 980, 472, 732, 92, 616, 744, 872, 108, 500, 756, 504}\n",
            "sum:25892, len:48\n",
            "=================\n",
            "diff:48\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}